{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import Counter\n",
    "from ML.metrics import accuracy_score\n",
    "from ML.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTreeClassifier():\n",
    "\n",
    "    def __init__(self, max_depth=2, min_samples_leaf = 1):\n",
    "        self.tree_ = None\n",
    "        self.max_depth = max_depth\n",
    "        self.min_samples_leaf = min_samples_leaf\n",
    "\n",
    "    def fit(self, X, y):\n",
    "        '''训练函数'''\n",
    "        self.tree_ = self.create_tree(X,y)\n",
    "        return self\n",
    "\n",
    "    def predict(self, X):\n",
    "        '''预测函数'''\n",
    "        assert self.tree_ is not None, '请先调用fit()方法'\n",
    "        return np.array([self._predict(x, self.tree_) for x in X])\n",
    "\n",
    "    def _predict(self, x, node):\n",
    "        if node.label is not None:\n",
    "            return node.label\n",
    "        if x[node.dim] <= node.v:\n",
    "            return self._predict(x, node.children_left)\n",
    "        else:\n",
    "            return self._predict(x,node.children_right)\n",
    "\n",
    "    def create_tree(self, X, y, current_depth = 1):\n",
    "        '''构建树节点函数'''\n",
    "        if current_depth > self.max_depth:\n",
    "            return None\n",
    "        \n",
    "        g, d, v = try_split(X,y,self.min_samples_leaf)\n",
    "        if d == -1 or g == 0:\n",
    "            return None\n",
    "        node = Node(d, v, g)\n",
    "        X_left, X_right, y_left, y_right = cut(X,y,d,v)\n",
    "        \n",
    "        node.children_left = self.create_tree(X_left, y_left, current_depth + 1)\n",
    "        if node.children_left is None:\n",
    "            label = Counter(y_left).most_common(1)[0][0]\n",
    "            node.children_left = Node(l=label)\n",
    "        \n",
    "        node.children_right = self.create_tree(X_right, y_right, current_depth + 1)\n",
    "        if node.children_right is None:\n",
    "            label = Counter(y_right).most_common(1)[0][0]\n",
    "            node.children_right = Node(l=label)\n",
    "            \n",
    "        return node\n",
    "\n",
    "    def score(self,X_test,y_test):\n",
    "        '''模型评分函数'''\n",
    "        y_predict = self.predict(X_test)\n",
    "        return accuracy_score(y_test, y_predict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node():\n",
    "    '''树节点类'''\n",
    "    def __init__(self, d=None, v=None, g=None, l=None):\n",
    "        self.dim = d\n",
    "        self.v = v\n",
    "        self.g = g\n",
    "        self.label = l\n",
    "        \n",
    "        self.children_left = None\n",
    "        self.children_right = None\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return 'Node(d={},v={},g={},l={})'.format(self.dim,self.v,self.g,self.label)\n",
    "\n",
    "def gini(y):\n",
    "    '''计算基尼系数函数'''\n",
    "    counter = Counter(y)\n",
    "    result = 0\n",
    "    for v in counter.values():\n",
    "        result += (v / len(y)) ** 2\n",
    "    return 1 - result\n",
    "\n",
    "def cut(X, y, d, v):\n",
    "    '''截断函数'''\n",
    "    ind_left = (X[:,d] <= v)\n",
    "    ind_right = (X[:,d] > v)\n",
    "    return X[ind_left], X[ind_right], y[ind_left], y[ind_right]\n",
    "\n",
    "def try_split(X,y,min_samples_leaf):\n",
    "    '''拆分函数'''\n",
    "    best_g = 1\n",
    "    best_d = -1\n",
    "    best_v = -1\n",
    "    for d in range(X.shape[1]):\n",
    "        sorted_index = np.argsort(X[:,d])\n",
    "        for i in range(len(X) - 1):\n",
    "            if X[sorted_index[i],d] == X[sorted_index[i+1],d]:\n",
    "                continue\n",
    "            v = (X[sorted_index[i],d] + X[sorted_index[i+1],d]) / 2\n",
    "            #print('d={},v={}'.format(d,v))\n",
    "            X_left,C_right,y_left,y_right = cut(X,y,d,v)\n",
    "            g_all = gini(y_left) + gini(y_right)\n",
    "            #print('d={},v={},g_all={}'.format(d,v,g_all))\n",
    "            if g_all < best_g and len(y_left) >= min_samples_leaf and len(y_right) >= min_samples_leaf:\n",
    "                best_g = g_all\n",
    "                best_d = d\n",
    "                best_v = v\n",
    "    return best_g,best_d,best_v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.导入数据并拆分训练数据和预测数据"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.loadtxt('data/x.txt')\n",
    "y = np.loadtxt('data/y.txt')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.25,seed=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.机器学习训练数据,建立模型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "dt_clf = DecisionTreeClassifier(max_depth=4, min_samples_leaf = 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.DecisionTreeClassifier at 0x9bab270>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dt_clf.fit(X_train,y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.预测并计算模型对预测数据的评分"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9459459459459459"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dt_clf.score(X_test,y_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.用网格搜索对参数max_depth,min_samples_leaf进行调优"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_score:0.9459459459459459,best_depth:2,best_samples_leaf:1\n"
     ]
    }
   ],
   "source": [
    "best_score = 0\n",
    "best_depth = 0\n",
    "best_samples_leaf = 0\n",
    "for depth in range(1,20):\n",
    "    for samples_leaf in range(1,20):\n",
    "        dt_clf = DecisionTreeClassifier(max_depth=depth, min_samples_leaf = samples_leaf)\n",
    "        dt_clf.fit(X_train,y_train)\n",
    "        score = dt_clf.score(X_test,y_test)\n",
    "        if score > best_score:\n",
    "            best_score = score\n",
    "            best_depth = depth\n",
    "            best_samples_leaf = samples_leaf\n",
    "\n",
    "print('best_score:{},best_depth:{},best_samples_leaf:{}'.format(best_score,best_depth,best_samples_leaf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
